ABC139 E League
問題
解説放送を見てそれを簡単にまとめた.
解法
試合ができる(対戦したい相手が自分と対戦したい)ときはしてよい. これを愚直に実装することで正しい解は求まるが,$ \Theta(N^3)かかるので間に合わない. この問題には2つの解法がある.
1. queue
提出
ここで, 次に試合が行われるというのをqueueに突っ込むことを考える. 1つの試合によって変化するのは対戦した人だけなので, 間に合う(変化分だけ見る). なお, queueはvectorで代用可能である. 提出参考.
2. グラフ
提出
各試合にIDをつけ, $ A_{i,j}についてそれぞれどの試合に使われるかでIDを振る. すると, $ N個の試合の順序についての不等式ができる. この不等式をすべて満たせば達成できる.
これは実はグラフに帰着出来る. まず不等式の関係を有向辺で表す. 条件より, DAGになっていないといけない(閉路があると割り当てることができない). DAGのときは最長経路問題という有名問題を解くことで答えが求まる. これにはトポロジカルソートを使う.
感想
かなり難しかった. 最長経路問題とかは典型なのに知らなかった. 特に2の解法はおさえておきたい.